package ans.p169;

/**
 * #      169
 * 名称   多数元素
 * 链接   https://leetcode-cn.com/problems/majority-element
 * 题解   [1670](https://leetcode-cn.com/problems/majority-element/solution)
 * 通过率 65.9%
 * 难道   简单
 */
//todo Boyer-Moore算法
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

}